﻿#pragma once
#include "Index.h"

#include "FlightBooking.h" //航班预定统计
#include "ReplaceSpace.h" //替换空格
#include "TowQueueMakeStack.h" //用两个队列实现栈
#include "PartitionList.h" //分隔链表
#include "AddByBits.h" //仅使用位运算实现两数相加

/**
 * 平衡括号字符串的最少插入次数.
 * https://leetcode.cn/problems/minimum-insertions-to-balance-a-parentheses-string/
 */
class MinInsertToBalanceParenStr
{
private:
	void validWithInsert(std::vector<char>& checker,int& insertCnt)
	{
		while (!checker.empty())
		{
			switch (checker.back())
			{
			case '(':
				insertCnt += 2;
				checker.pop_back();
				break;
			case ')': 
				checker.pop_back();
				if (checker.empty())
					insertCnt += 2;
				else //validChecker.back()=='(' 或 ')'
				{
					checker.pop_back();
					insertCnt += 1;
				}
			}
		}
	}
public:
	int minInsertions(std::string s)
	{
		if (s.empty())
			return 0;
		const int strSize = s.size();
		int insertCnt = 0;
		
		std::vector<char> checker;
		for (int i = 0; i < std::min<int>(2, strSize); ++i)
			checker.push_back(s[i]);

		for(int i=2;i<strSize;++i)
		{
			const char pre = checker.empty() ? ' ' : checker.back();
			checker.push_back(s[i]);

			const int lastIndex = checker.size() - 1;
			if(lastIndex>=2 && checker[lastIndex]==')' && checker[lastIndex-1]==')' && checker[lastIndex-2]=='(')
			{
				checker.pop_back();
				checker.pop_back();
				checker.pop_back();
			}

			if(!checker.empty() && checker.back()=='(' && !(pre==' '||pre=='('))
			{
				checker.pop_back();
				validWithInsert(checker, insertCnt);
				checker.push_back('(');
			}
		}

		validWithInsert(checker, insertCnt);
		
		return insertCnt;
	}
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(MinInsertToBalanceParenStrTest, minInsertions)
{
	MinInsertToBalanceParenStr solution;
	ASSERT_EQ(solution.minInsertions("(()))(()))()())))"), 4);
}
#endif